package week01;

/**
 * 旋转数组
 * 给定一个数组，将数组中的元素向右移动k个位置，其中k是非负数。
 * <p>
 * <p>
 * 进阶：
 * <p>
 * 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
 * 你可以使用空间复杂度为O(1)的原地算法解决这个问题吗？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/rotate-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Code02 {

    /**
     * 环形替换
     *
     * @param nums nums
     * @param k    k
     */
    public void way01(int[] nums, int k) {
        if (nums == null || nums.length < 2 || k < 1) {
            return;
        }
        k = k % nums.length;
        int count = 0;
        for (int i = 0; count < nums.length; i++) {
            int cur = i;
            int pre = nums[cur];
            do {
                int next = (cur + k) % nums.length;
                int tmp = nums[next];
                nums[next] = pre;
                pre = tmp;
                count++;
                cur = next;
            } while (i != cur);
        }
    }

    /**
     * 数组反转
     *
     * @param nums nums
     * @param k    k
     */
    public void way02(int[] nums, int k) {
        if (nums == null || nums.length < 2 || k < 1) {
            return;
        }
        int length = nums.length;
        reverse(nums, 0, length - 1);
        reverse(nums, 0, k % length - 1);
        reverse(nums, k % length, length - 1);
    }

    /**
     * 使用一个临时数组
     *
     * @param nums nums
     * @param k    k
     */
    public void way03(int[] nums, int k) {
        if (nums == null || nums.length < 2 || k < 1) {
            return;
        }
        int length = nums.length;
        int[] newArray = new int[length];
        for (int i = 0; i < length; i++) {
            newArray[(i + k) % length] = nums[i];
        }
        System.arraycopy(newArray, 0, nums, 0, length);
    }

    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int tmp = nums[left];
            nums[left++] = nums[right];
            nums[right--] = tmp;
        }
    }
}
